package linkList;

import java.util.ArrayList;
import java.util.List;

public class N234_isPalindrome {
    // 链表转数组再判断
    public boolean isPalindrome_Array(ListNode head) {
        List<Integer> list = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next)
            list.add(p.val);

        int left = 0, right = list.size() - 1;
        while (left < right) {
            if (list.get(left).equals(list.get(right))) return false;
            left++;
            right--;
        }
        return true;
    }

    // 翻转一半链表判断
    public boolean isPalindrome_Reverse(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head, fast = head;
        ListNode pre = head, prepre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            pre.next = prepre;
            prepre = pre;
        }
        if (fast != null) {
            slow = slow.next;
        }
        while (pre != null && slow != null) {
            if (pre.val != slow.val) return false;
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }

}
